package 二分搜索法;

public class No33搜索旋转排序数组 {

    /**
     * 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转
     * （例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
     * 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
     *
     * 示例 1：
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     * 示例 2：
     * 输入：nums = [4,5,6,7,0,1,2], target = 3
     * 输出：-1
     * 示例 3：
     * 输入：nums = [1], target = 0
     * 输出：-1
     *
     * 提示：
     * 1 <= nums.length <= 5000
     * -10^4 <= nums[i] <= 10^4
     * nums 中的每个值都 独一无二
     * nums 肯定会在某个点上旋转
     * -10^4 <= target <= 10^4
     */

    public int search(int[] nums, int target) {
        if(nums.length<1){
            return -1;
        }
        if(nums.length<2){
            return nums[0]==target?0:-1;
        }
        if(nums[0]<nums[nums.length-1]){
            //已是排列好的顺序
            return binarySearch(nums,target,0,nums.length-1);
        }
        //没有排列好,那就找到断层,然后开始排列

        int left=0;
        int right=nums.length-1;
        int index=-1;
        while (left<=right){

            int mid=left+(right-left)/2;
            int midNum=nums[mid];

            if(nums[mid]>nums[mid+1]){
                //mid
                index=mid;
                break;
            }else if(nums[mid]<nums[mid-1]){
                //mid-1
                index=mid-1;
                break;
            } else if (nums[left]<midNum){
                //去右边
                left=mid+1;
            }else{
                //去左边
                right=mid-1;
            }

        }

        if(index==-1){
            return -1;
        }

        if(target>nums[index]){
            return -1;
        }else if(target>=nums[0]){
            //去左边找
            return binarySearch(nums,target,0,index);
        }else{
            //去右边找
            return binarySearch(nums,target,index+1,nums.length-1);
        }
    }

    private int binarySearch(int[] arr,int target,int left,int right){

        while (left<=right){

            int mid=left+(right-left)/2;
            int midNumber=arr[mid];

            if(midNumber<target){
                //去右边
                left=mid+1;
            }else if(midNumber>target){
                //去左边
                right=mid-1;
            }else{
                return mid;
            }

        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr={5,4};
        No33搜索旋转排序数组 n=new No33搜索旋转排序数组();
        int result = n.search(arr, 4);
        System.out.println(result);
    }

}
